In many applications, it is desirable for one computer, server, mobile telephone, RFID tag or other type of cryptographic device to pair with, authenticate or otherwise share secrets such as keys with another cryptographic device. Unfortunately, such arrangements can be problematic when carried out using existing techniques.
For example, a conventional pairing protocol that relies on breakable ciphers is disclosed in G. T. Amariucai et al., “An Automatic, Time-Based, Secure Pairing Protocol for Passive RFID,” RFIDSec, 2011, which is incorporated by reference herein. This known pairing protocol is referred to as an “adopted pet” or AP protocol. In the AP protocol, an RFID tag gradually leaks a secret key, such that a reader in proximity to the tag for an extended period of time can learn the secret key. However, a reader that receives tag outputs over only limited-duration intervals of time cannot learn the secret key. Thus, for instance, a tag in a user's home might pair with a reader there overnight, while a maliciously operated reader in a commuter bus would not have sufficient time to harvest the secret key from the tag.
The AP protocol leaks the secret key through a key stream generated by a cryptographically weak pseudorandom number generator (PRNG), such as a linear-feedback shift register (LFSR), seeded by the secret key. By harvesting enough contiguous key stream data, a reader can break the PRNG and recover the secret key. However, this reliance on breakable ciphers has a number of significant drawbacks. For example, breakable ciphers can be difficult to implement in practice, and their security level is difficult to calibrate. Also, requiring the use of breakable ciphers means that the AP protocol will not work with strong, standard ciphers such as the Advanced Encryption Standard (AES). Furthermore, the AP protocol does not permit a flexible range of security policies.